package com.example.question.bt.backtrack1;

import java.util.ArrayList;
import java.util.List;

/**
 * @Date 2023-07-16
 * @Author Jonathan
 */
public class Code10_93 {

    public static void main(String[] args) {
        Code10_93 code = new Code10_93();
        System.out.println(code.restoreIpAddresses("101023"));
    }

    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        if (s == null || s.length() < 4) {
            return res;
        }
        dfs(s, 0, new ArrayList<>(), res);
        return res;
    }


    private void dfs(String s, int index, List<String> paths, List<String> res) {

        if (paths.size() == 4 && s.length() == index) {
            res.add(String.join(".", paths));
            return;
        }
        //  取下来的长度可能是 1,2,3
        for (int segLen = 1; segLen < 4; segLen++) {
            if (index + segLen > s.length()) {
                break;
            }
            // 这个是substring的操作是耗费性能的
            String substring = s.substring(index, index + segLen);
            if (!isValidIpSegment(substring)) {
                continue;
            }
            paths.add(substring);
            dfs(s, index + segLen, paths, res);
            paths.remove(paths.size() - 1);
        }
    }


    /**
     * 判断ip段是不是合法
     */
    private boolean isValidIpSegment(String segment) {
        int len = segment.length();
        if (len > 3) {
            return false;
        }

        // 1.ip段如果是以0开头的话 那么这个ip段只能是0
        if (segment.charAt(0) == '0') {
            return len == 1;
        }
        // 2.ip段需要小于等于255
        return Integer.parseInt(segment) <= 255;
    }
}
